package 优先算法.递归_搜索与回溯.二叉树深度搜索.二叉搜索树中第K小的元素;


/**
 *https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        Solution.TreeNode root = new Solution.TreeNode(3);
        root.left = new Solution.TreeNode(1);
        root.right = new Solution.TreeNode(4);
//        root.left.left = new Solution.TreeNode(0);
        root.left.right = new Solution.TreeNode(2);

        int rel = so.kthSmallest(root,1);
        System.out.println(rel);
//        printTree(rel); // 打印剪枝后的树
    }
    private static void printTree(Solution.TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        printTree(node.left);
        printTree(node.right);
    }
}
class Solution {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public Integer rel = 0;
    public Integer count;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return rel;
    }
    public void dfs(TreeNode root) {
        if(root == null) return;

        //剪枝
        if(count == 0) return;
        dfs(root.left);

        count--;
        if(count == 0){
            rel = root.val;
        }

        //剪枝
        if(count == 0) return;
        dfs(root.right);
    }
}
